package java_thinking.unit_16.source;

/**
 * @Desc:   单轴快排测试-双端扫描交换方式
 *          结合 1.单轴快排-双端扫描交换方式-图解.png看
 * @author: cww
 * @DateTime: 2019/4/23 19:14
 */

public class SingleSwapSort {
    public static void main(String[] args) {
        int[] a1 = {5,9,1,1,2,9,8,1,3,5,15,22,1,8};
        deScanSwapSort(a1);
    }
    public static void deScanSwapSort(int[] items) {
        deScanSwapSort(items,0,items.length -1);
//        System.out.println(Arrays.toString(items));
    }

    public static void deScanSwapSort(int[] items,int start,int end) {
        if (start < end) {
            int pivot = items[start];
            int i = start +1,j = end;
            while (i <= j) {
                while (i <= j) {
                    while (i <= j && items[i] < pivot) {
                        i++;
                    }
                    while (i <= j && items[j] >= pivot) {
                        j--;
                    }
                    if (i <= j) {
                        swap(items, i, j);
                    }
                }
            }
            //中心点交换到中间,j总是停在从右到左最后pivot小的第一个地方结束
            swap(items,start,j);
            //中心点左半部分递归
            deScanSwapSort(items, start,j -1);
            //中心点右半部分递归
            deScanSwapSort(items,j + 1, end);
        }

    }

    public static void swap(int[] items, int i, int j) {
        int tmp = items[i];
        items[i] = items[j];
        items[j] = tmp;
    }
}
